def insert_sort(nums):
    for i in range(0, len(nums) - 1):
        for j in range(i, -1, -1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]


def shell_sort(nums):
    gap = 6
    while gap > 1:
        gap = gap // 3 + 1
        for i in range(0, len(nums) - gap):
            for j in range(i, -1, -gap):
                if nums[j] > nums[j + gap]:
                    nums[j], nums[j + gap] = nums[j + gap], nums[j]


def select_sort(nums):
    left = 0
    right = len(nums) - 1
    while left < right:
        mini = left
        maxi = left
        for i in range(left + 1, right + 1):
            if nums[i] < nums[mini]:
                mini = i
            if nums[i] > nums[maxi]:
                maxi = i
        nums[left], nums[mini] = nums[mini], nums[left]
        if left == maxi:
            maxi = mini
        nums[right], nums[maxi] = nums[maxi], nums[right]
        left += 1
        right -= 1


def ajust_down(nums, size, parent):
    child = parent * 2 + 1
    while child < size:
        if child + 1 < size and nums[child] < nums[child + 1]:
            child += 1
        if nums[parent] < nums[child]:
            nums[parent], nums[child] = nums[child], nums[parent]
            parent = child
            child = parent * 2 + 1
        else:
            break


def heap_sort(nums):
    for i in range((len(nums) - 1 - 1) // 2, -1, -1):
        ajust_down(nums, len(nums), i)
    end = len(nums) - 1
    while end > 0:
        nums[0], nums[end] = nums[end], nums[0]
        ajust_down(nums, end, 0)
        end -= 1


num = [9, 1, 4, 7, 2, 8, 3, 6, 5]
# insert_sort(num)
# shell_sort(num)
# select_sort(num)
# heap_sort(num)
print(num)

